package com.cg.offer;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * 剑指Offer 48.最长不含重复字符的子字符串
 *
 * @program: LeetCode->Offer_48
 * @description: 剑指Offer 48.最长不含重复字符的子字符串
 * @author: cg
 * @create: 2022-03-18 18:59
 **/
public class Offer_48 {

    @Test
    public void test48() {
        System.out.println(lengthOfLongestSubstring("abcabcbb"));
        System.out.println(lengthOfLongestSubstring(" "));
        System.out.println(lengthOfLongestSubstring("bbbbb"));
    }

    /**
     * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
     * <p>
     * 示例 1:
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * <p>
     * 示例 2:
     * 输入: "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * <p>
     * 示例 3:
     * 输入: "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     * <p>
     * 提示：
     * s.length <= 40000
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        /*Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
            // 获取索引 i
            int i = dic.getOrDefault(s.charAt(j), -1);
            // 更新哈希表
            dic.put(s.charAt(j), j);
            // dp[j - 1] -> dp[j]
            tmp = tmp < j - i ? tmp + 1 : j - i;
            // max(dp[j - 1], dp[j])
            res = Math.max(res, tmp);
        }
        return res;*/
        Deque<Character> deque = new ArrayDeque<>();
        char[] chars = s.toCharArray();
        int max = 0;
        for (int i = 0; i < chars.length; i++) {
            // 队列中存在该数
            if (deque.contains(chars[i])) {
                max = Math.max(max, deque.size());
                // 一直删到这个相同数的前一个
                while (deque.peekFirst() != null && deque.peekFirst() != chars[i]) {
                    deque.removeFirst();
                }
                // 删除相同的这个数
                deque.removeFirst();
            }
            // 将当前数加入队列
            deque.addLast(chars[i]);
        }
        max = Math.max(max, deque.size());
        return max;
    }

}
